package www.study.com;

//K 个一组翻转链表 https://leetcode.cn/problems/reverse-nodes-in-k-group/
public class code24 {
    public static void main(String[] args) {

    }

    public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    class Solution {
        public ListNode reverseKGroup(ListNode nowPos, int k) {
            ListNode res = null;
            ListNode[] infos = reverse(nowPos,k);
            /**
             * 之前的错误：
             * if(info == null || info[2] == null) return nowPos;
             * 当info[2] == null的时候不能够返回nowPos，比如链表 1->2>3，k为3，反转之后 3->2->1，此时info[2]为空，如果
             * 返回nowPos的话，结果会是1，而不是反转之后的3->2->1
             */
            if(infos == null) return nowPos;
            ListNode head = infos[0];
            ListNode tail = infos[1];
            ListNode nextk1 = infos[2];
            tail.next = reverseKGroup(nextk1,k);
            return head;
        }
        //将nowPos链表前k个反转，并返回反转后的头、尾节点、nowPos链表第k+1个节点
        //1->2->3->4->5 反转5->4->3->2->1 头节点5，尾节点1，如果链表不足k个，直接返回null
        public ListNode[] reverse(ListNode nowPos, int k){
            ListNode pre = null;
            ListNode now = nowPos;
            ListNode next = null;
            ListNode nodeK1 = null;
            int cnt = 0;
            while(cnt < k && now != null){
                cnt++;
                if(cnt == k) nodeK1 = now.next;
                next = now.next;
                now.next = pre;
                pre = now;
                now = next;
            }
            if(cnt != k){ //如果不足k个，就反转回去
                reverse(pre,cnt);
                return null;
            }
            ListNode[] res = new ListNode[3];
            res[0] = pre;res[1] = nowPos;res[2] = nodeK1;
            return res;
        }
    }
}
